#include <iostream>

using namespace std;

// 2.两数相加
// 给你两个 非空 的链表，表示两个非负的整数。
// 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x, ListNode *next): val(x), next(next) {}
};
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr)
            return l2;
        if(l2 == nullptr)
            return l1;

        int c = 0; // 进位数
        ListNode *pa = l1, *pb = l2;
        ListNode *res = new ListNode(-1);   // 虚拟头结点，结果指针
        ListNode *tailRes = res;
        int subSum = 0;
        while(pa != nullptr && pb != nullptr) {
            subSum = pa->val + pb->val + c;
            if(subSum >= 10) {
                c = subSum / 10;
                tailRes->next = new ListNode(subSum % 10);
                tailRes = tailRes->next;
            } else {
                c = 0;
                tailRes->next = new ListNode(subSum);
                tailRes = tailRes->next;
            }
            pa = pa->next;
            pb = pb->next;
        }
        while(pa != nullptr || pb != nullptr) {
            if(pa != nullptr)
                subSum = pa->val + c;
            if(pb != nullptr)
                subSum = pb->val + c;
            if(subSum >= 10) {
                c = subSum / 10;
                tailRes->next = new ListNode(subSum % 10);
                tailRes = tailRes->next;
            } else {
                c = 0;
                tailRes->next = new ListNode(subSum);
                tailRes = tailRes->next;
            }
            if(pa != nullptr)
                pa = pa->next;
            if(pb != nullptr)
                pb = pb->next;
        }
        if(c == 1)
            tailRes->next = new ListNode(1, nullptr);

        ListNode *retNode = res->next;
        delete res;
        return retNode;
    }
};

// 根据n个元素的数组arr创建一个链表, 并返回链表的头
ListNode* createLinkedList(int arr[], int n){

    if(n == 0)
        return nullptr;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for(int i = 1 ; i < n ; i ++){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}

// 打印以head为头结点的链表信息内容
void printLinkedList(ListNode* head){

    ListNode* curNode = head;
    while(curNode != nullptr){
        cout << curNode->val << " -> ";
        curNode = curNode->next;
    }

    cout << "NULL" << endl;
}

// 释放以head为头结点的链表空间
void deleteLinkedList(ListNode* head){

    ListNode* curNode = head;
    while(curNode != nullptr){
        ListNode* delNode = curNode;
        curNode = curNode->next;
        delete delNode;
    }
}

int main() {
    int arr1[] = {2,4,3}, arr2[] = {5,6,4};
    int n1 = sizeof(arr1)/sizeof(int);
    int n2 = sizeof(arr2)/sizeof(int);

    ListNode* l1 = createLinkedList(arr1, n1);
    ListNode* l2 = createLinkedList(arr2, n2);

    printLinkedList(l1);
    printLinkedList(l2);

    ListNode *l3 = Solution().addTwoNumbers(l1, l2);
    printLinkedList(l3);

    cout << "==================" << endl;
    int arr3[] = {9,9,9,9,9,9,9}, arr4[] = {9,9,9,9};
    n1 = sizeof(arr3)/sizeof(int);
    n2 = sizeof(arr4)/sizeof(int);

    l1 = createLinkedList(arr3, n1);
    l2 = createLinkedList(arr4, n2);

    printLinkedList(l1);
    printLinkedList(l2);

    l3 = Solution().addTwoNumbers(l1, l2);
    printLinkedList(l3);
    return 0;
}
